这道题边的数量最高是10000多,而点只有500,这提醒我们,我们不能直接对边求期望,而是点。
设表示点的期望走过次数,表示点的度数。
那么,
但是,你会发现,要依靠,不能直接计算。
再次观察后,既然每一项都有其他项,类似方程形式,那我们可以用高斯消元解决,计算出每一点的。
然后,我们先不考虑边权,根据点算出边的期望,当点之间存在一条边时,这条边显然只与点有关,且该边的期望为:
之后,利用贪心的思想,期望经过值越大,我们就分配越小的权值,统计一下答案就好了。
注意:边数可达点数平方/2,跟边有关的数组开 的平方。
// luogu-judger-enable-o2
#include <cstdio>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define eps 1e-10
const int MAXN = 500;
int n , m , u , v , Degree[ MAXN + 5 ] , S[ MAXN * MAXN ] , T[ MAXN * MAXN ];
double a[ MAXN + 5 ][ MAXN + 5 ] , Expection[ MAXN * MAXN + 5 ]; //a数组为点i到点n,点i的期望走过次数
vector< int > Graph[ MAXN + 5 ];
void Gauss( ) {
int Row , Column;
for( int i = 1 ; i < n ; i ++ ) {
Column = i;
for( int j = i ; j <= n ; j ++ )
if( fabs( a[ j ][ i ] ) > fabs( a[ Column ][ i ] ) )
Column = j;
swap( a[ i ] , a[ Column ] );
for( int j = n ; j >= i ; j -- )
a[ i ][ j ] /= a[ i ][ i ];
for( int j = 1 ; j < n ; j ++ )
if( i != j )
for( int k = n ; k >= i ; k -- )
a[ j ][ k ] -= a[ j ][ i ] * a[ i ][ k ];
}
}
int main( ) {
scanf("%d %d",&n,&m);
for( int i = 1 ; i <= m ; i ++ ) {
scanf("%d %d",&u,&v);
Degree[ u ] ++ , Degree[ v ] ++;
Graph[ u ].push_back( v );
Graph[ v ].push_back( u );
S[ i ] = u , T[ i ] = v;
}
a[ 1 ][ n ] = 1;
for( int i = 1 ; i < n ; i ++ ) {
a[ i ][ i ] = 1;
for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ ) {
int v = Graph[ i ][ j ];
if( v != n ) a[ i ][ v ] = -1.0 / Degree[ v ];
}
}
Gauss( );
for( int i = 1 ; i <= m ; i ++ ) {
if( S[ i ] != n )
Expection[ i ] += a[ S[ i ] ][ n ] * ( 1.0 / Degree[ S[ i ] ] );
if( T[ i ] != n )
Expection[ i ] += a[ T[ i ] ][ n ] * ( 1.0 / Degree[ T[ i ] ] );
}
sort( Expection + 1 , Expection + m + 1 );
double Ans = 0;
for( int i = 1 ; i <= m ; i ++ )
Ans += Expection[ i ] * 1.0 * ( m - i + 1 );
printf("%.3lf",Ans);
return 0;
}